package com.algorithms.hash;

import com.algorithms.utils.Utils;

@SuppressWarnings("unchecked")
public class DoubleHashTable<T> {
	private HashItem<T>[] hashList;
	private int size;
	
	public DoubleHashTable(int size){
		this.size = Utils.getSmallestPrime(size);
		this.hashList = new HashItem[this.size];
	}
	
	/**
	 * insert an item to hash
	 * 
	 * @param key
	 * @param data
	 */
	public void insert(int key, T data){
		int hashVal = hashFunc1(key);
		int stepSize = hashFunc2(key);
		int numOfSteps = 0;
		
		while (hashList[hashVal] != null &&
				numOfSteps < this.size){
			// jump to the next potential position
			hashVal += stepSize;
			
			// wrap around
			hashVal %= this.size; 
			
			// check if number of step is over the size
			numOfSteps++;
		}
		
		// found a position to insert
		hashList[hashVal] = new HashItem<T>(key, data);
	}
	
	/**
	 * find item by key in hash
	 * 
	 * @param key
	 * @return
	 */
	public T find(int key){
		int hashVal = hashFunc1(key);
		int stepSize = hashFunc2(key);
		int numOfSteps = 0;
		
		while (hashList[hashVal] != null && numOfSteps < this.size){
			if (hashList[hashVal].getKey() == key){
				// found item
				return hashList[hashVal].getData();
			}
			hashVal += stepSize;
			hashVal %= this.size;
			
			// check if number of step is over the size
			numOfSteps++;
		}
		
		return null;
	}
	
	public boolean delete(int key){
		int hashVal = hashFunc1(key);
		int stepSize = hashFunc2(key);
		int numOfSteps = 0;
		
		while (hashList[hashVal] != null && numOfSteps < this.size){
			if (hashList[hashVal].getKey() == key){
				// item found
				hashList[hashVal] = null;
				return true;
			}
			hashVal += stepSize;
			hashVal %= this.size;
			
			// check if number of step is over the size
			numOfSteps++;
		}
		// item not found
		return false;
	}
	
	public void printHash(){
		System.out.print("table: ");
		for (int i = 0; i < this.size; i++){
			if (this.hashList[i] != null){
				System.out.print(this.hashList[i].getKey() + " ");
			}else{
				System.out.print("** ");
			}
		}
		System.out.println();
	}
	
	/**
	 * map a key from real data to an index on hash list
	 * 
	 * @param key
	 * @return new potential index
	 */
	private int hashFunc1(int key){
		return key % this.size;
	}
	
	/**
	 * find a step to jump when potential position is already filled
	 * 
	 * @param key
	 * @return step to jump
	 */
	private int hashFunc2(int key){
		return 5 - (key % 5);
	}
}
